package com.gorkr.dp.pack;

/**
 * @author gorkr
 * @date 2022/06/18 18:12
 **/
public class M518CoinChange2 {

    public int change(int amount, int[] coins) {

        // dp[i][j]  前i中硬币凑出j面额有几种方法
        int[][] dp = new int[coins.length + 1][amount + 1];
        for (int i = 0; i <= coins.length; i++) {
            dp[i][0] = 1;
        }

        // base case
        for (int i = 1; i <=coins.length; i++) {
            for (int j = 1; j <=amount; j++) {
                if(coins[i-1]>j){
                    dp[i][j] = dp[i-1][j];
                }else {
                    dp[i][j] = dp[i-1][j] + dp[i][j-coins[i-1]];
                }
            }
        }
        return dp[coins.length][amount];
    }

}
    